
/* 
 * Copyright (C) 1997 Roger Whitney <whitney@cs.sdsu.edu>
 *
 * This file is part of the San Diego State University Java Library.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

package edu.sdsu.util;

import java.util.LinkedList;
import java.util.Vector;

import edu.sdsu.util.Comparer;

/**
 * A SortedList is a list of objects kept in sorted order. A Comparer object is
 * needed to compare objects in the list, as there is no standard compare
 * operation for objects. Comparer class for standard types are found in the
 * package sdsu.compare. For object types not covered, make a sublclass of
 * sdsu.compare.Comparer;
 * 
 * @see List
 * @see Comparer
 * @see SortedCollection
 * @version 1.0 5 June 1997
 * @author Roger Whitney (<a
 *         href=mailto:whitney@cs.sdsu.edu>whitney@cs.sdsu.edu</a>)
 */

public class SortedList<T> extends LinkedList<T> implements SortedCollection<T> {
	/**
	 * 
	 */
	private static final long serialVersionUID = 1L;
	protected Comparer<T> order;

	/**
	 * Create a new SortedList using the Comparer object listOrder to define the
	 * order on elements. The sortedlist will have room for initialSize elements
	 * before it needs to grow.
	 */
	public SortedList(Comparer<T> listOrder) {
		order = listOrder;
	}

	/**
	 * Returns the comparer object used to order list.
	 */
	public Comparer<T> getComparer() {
		return order;
	}

	/**
	 * Adds the specified object in proper location to keep list sorted.
	 * 
	 * @param elementToAdd
	 *            the element to be added
	 */
	public void addElement(T elementToAdd) {
		super.add( insertionIndexOf(elementToAdd), elementToAdd );
	}
	
	public void addElements(SortedList<T> elementsToAdd) {
		addArray(elementsToAdd.toArray());
	}

	/**
	 * Adds the elements of a SortedCollection to a SortedList. Resulting list
	 * is sorted
	 * 
	 * @param elementsToAdd
	 *            the elements to be added
	 */
	public void addElements(SortedCollection<T> elementsToAdd) {
		if (order.equals(elementsToAdd.getComparer())) {
			T array[] = (T[])merge(toArray(), size(), elementsToAdd.toArray(),
					elementsToAdd.size());
			replaceElements(array);
		} else
			addArray(elementsToAdd.toArray());
	}
	
	

	/**
	 * Adds the elements of a Vector to a SortedList. Resulting list is sorted
	 * 
	 * @param elementsToAdd
	 *            the elements to be added
	 */
	public void addElements(Vector<T> elementsToAdd) {
		T[] rawElements = (T[])new Object[elementsToAdd.size()];
		elementsToAdd.copyInto(rawElements);
		addArray(rawElements);
	}

	/**
	 * Adds the elements of an array to a SortedList. Resulting list is sorted
	 * 
	 * @param elementsToAdd
	 *            the elements to be added
	 */
	public void addElements(T[] elementsToAdd) {
		T[] sortable = (T[])new Object[elementsToAdd.length];
		System.arraycopy(elementsToAdd, 0, sortable, 0, elementsToAdd.length);
		addArray(sortable);
	}

	/**
	 * Searches for the specified object, starting at the specified position and
	 * returns an index to it.
	 * 
	 * @param elem
	 *            the desired element
	 * @param index
	 *            the index where to start searching
	 * @return the index of the element, or -1 if it was not found.
	 */
	public final int indexOf(T elem, int index) {
		Comparer<T> order = this.order; // local access is faster
		T[] elementData = (T[]) toArray();

		int searchIndex = nearBinarySearch(elementData, index, size() - 1, elem);

		// Find first occurance of the element
		while (searchIndex >= index) {
			if (order.greaterThan(elem, elementData[searchIndex]))
				break;
			searchIndex--;
		}

		if (order.equals(elem, elementData[searchIndex + 1]))
			return searchIndex + 1;
		else
			return -1;
	}


	/**
	 * Resorts the list using the new comparer to define the ordering of the
	 * elements.
	 */
	public void resort(Comparer<T> newOrder) {
		order = newOrder;
		T array[] = toArray();
		clear();
		addElements( array );
	}
	
	public void reinit( Comparer<T> newOrder ) {
		order = newOrder;
		clear();
	}

	/**
	 * Clones this list. The elements are <strong>not</strong> cloned.
	 */
	public SortedList<T> clone() {
		SortedList<T> v =  (SortedList<T>) super.clone();
		v.order = this.order;
		return v;
	}

	/**
	 * Adds an array of elements to the sorted list. Changes the array
	 * elementsToAdd
	 */
	protected void addArray(T[] elementsToAdd) {
		// Insertion sort is very good on small lists
		if (elementsToAdd.length < 10) {
			for (int index = 0; index < elementsToAdd.length; index++)
				addElement(elementsToAdd[index]);
		}

		else {
			T array[] = toArray();
			sort(array, 0, array.length - 1);
			T newArray[] = (T[])merge(array, array.length, elementsToAdd,
					elementsToAdd.length);
			replaceElements(newArray);
		}
	}

	/**
	 * Returns the result of merging the first leftLength elements of array left
	 * and the first rightLength elements of array right. Requires that left and
	 * right are sorted using current comparer object.
	 */
	protected Object[] merge(T left[], int leftLength, T[] right,
			int rightLenght) {
		int leftIndex = 0;
		int rightIndex = 0;
		int mergedIndex = 0;
		Comparer<T> order = this.order;

		Object[] merged = new Object[leftLength + rightLenght];

		while ((leftIndex < leftLength) && (rightIndex < rightLenght)) {
			if (order.greaterThan(left[leftIndex], right[rightIndex]))
				merged[mergedIndex++] = right[rightIndex++];
			else
				merged[mergedIndex++] = left[leftIndex++];
		}

		if (leftIndex >= leftLength)
			while (rightIndex < rightLenght)
				merged[mergedIndex++] = right[rightIndex++];
		else
			while (leftIndex < leftLength)
				merged[mergedIndex++] = left[leftIndex++];

		return merged;
	}

	/**
	 * Use binary serach to get near itemToFind in the array data. Only search
	 * between indexes startIndex and endIndex of data.
	 */
	private int nearBinarySearch(T[] data, int startIndex, int endIndex,
			T itemToFind) {
		Comparer<T> order = this.order;
		int lowIndex = startIndex;
		int highIndex = endIndex;

		// Just get close with binary search
		// Need to check for equal elements anyway and last bit
		// of binary search is slow
		while ((highIndex - lowIndex) > 3) {
			int midPoint = (highIndex + lowIndex) / 2;

			if (order.lessThan(itemToFind, data[midPoint]))
				highIndex = midPoint - 1;
			else if (order.greaterThan(itemToFind, data[midPoint]))
				lowIndex = midPoint + 1;
			else
				// found element,
				return midPoint;
		}
		return highIndex;
	}

	/**
	 * Sorts the list elements from lowIndex to highIndex
	 */
	protected void sort(T[] list, int lowIndex, int highIndex) {
		// Shell sort.
		Comparer<T> order = this.order;
		int stepSize = highIndex - lowIndex + 1;

		while (stepSize > 1) {
			if (stepSize < 5)
				stepSize = 1; // perform normal insertion sort
			else
				stepSize = (5 * stepSize - 1) / 11;

			// Do linear insertion sort from bottom to top in steps
			for (int sortChain = highIndex - stepSize; sortChain >= lowIndex; sortChain--) {
				T insertMe = list[sortChain];
				int k;
				for (k = sortChain + stepSize; k <= highIndex
						&& order.greaterThan(insertMe, list[k]); k += stepSize) {
					list[k - stepSize] = list[k];
				}

				list[k - stepSize] = insertMe;
			}
		}
	}

	protected int insertionIndexOf(T item) {
		int insertionPoint = super.size();
		while ((insertionPoint > 0)
				&& (order.lessThan(item, get(insertionPoint - 1))))
			insertionPoint--;
		return insertionPoint;
	}
	
	public void replaceElements (T elementsToAdd[])
    {
		clear();
		for (int i = 0; i < elementsToAdd.length; i++)
		{
		    addElement (elementsToAdd[i]);
		}

    }

	
	public T[] toArray() {
		return (T[]) super.toArray();
	}
}
